package 高频题;

import java.util.*;

public class 合并区间_56 {
    public int[][] merge(int[][] intervals) {
        List<int[]> arr = new ArrayList<int[]>();
        if (intervals.length == 0) {
            return new int[][]{};
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            //按照start升序排列
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        arr.add(intervals[0]);
        for (int i = 1; i < intervals.length; ++i) {
            //[x1,x2]和[y1,y2]比较，如果x2<y1说明这两个区间不相交
            if (arr.get(arr.size() - 1)[1] < intervals[i][0]) {
                arr.add(intervals[i]);
            }
            //否则，将这两个区间合并为 [x1,max(x2,y2)]，也就是新区间的end要保持最大
            else {
                arr.get(arr.size() - 1)[1] = Math.max(arr.get(arr.size() - 1)[1], intervals[i][1]);
            }
        }
        //为什么放0，0长度？可以看下源码就知道了
        return arr.toArray(new int[0][0]);
    }
}
